\section{Introducci\'on}

Para este problema, se nos da un tablero de \textbf{n} por \textbf{m} casillas y \textbf{n.m} piezas. Cada pieza tiene cuatro colores, uno arriba, otro abajo, uno a la derecha y otro a la izquierda.
\\
\\
Luego se nos pide que completemos el tablero con la mayor cantidad de piezas posibles, tal que los colores adyacentes de las piezas coincidan.
\\
\\
Para la resoluci\'on del problema contamos con los siguientes datos:

\begin{itemize}
\item Dos enteros \textbf{n} y \textbf{m} $\rightarrow$ Representar\'an el n\'umero de filas y de columnas del tablero.
\item Un entero \textbf{c} $\rightarrow$ Representar\'a cantidad de colores distintos en las piezas.
\item \textbf{n.m} piezas donde cada una de ellas tiene:
\begin{itemize}
\item Cuatro enteros \textbf{sup}, \textbf{izq}, \textbf{der}, \textbf{inf}  $\rightarrow$ Representar\'an los cuatro colores de cada uno de sus lados.
\end{itemize}
\end{itemize}

\subsection{Ejemplo Ilustrativo}

Una posible instancia del problema, podr\'ia ser: 
\\
\\
\textbf{n} $= 2$, \textbf{m} $= 2$, \textbf{c} $= 4$
\begin{itemize}
\item[\textbf{Pieza 1:}] $sup = 1$, $izq = 1$, $der = 1$, $inf = 1$
\item[\textbf{Pieza 2:}] $sup = 1$, $izq = 2$, $der = 2$, $inf = 2$
\item[\textbf{Pieza 3:}] $sup = 2$, $izq = 3$, $der = 1$, $inf = 3$
\item[\textbf{Pieza 4:}] $sup = 3$, $izq = 2$, $der = 4$, $inf = 1$
\end{itemize}
%\\
%\\
En este caso una posible soluci\'on ser\'ia la siguiente: $~~~$
\begin{tabular}{| l | l |}
\hline
~~~Salida~~~\\ \hline
$
\begin{vmatrix}
~~~2  & 4 ~~\\
~~~3  & 1 ~~\\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\\
\\
\\
Por supuesto este es un caso extremadamente sencillo, pero a\'un as\'i ya tenemos $4!=24$ diferentes permutaciones distintas que pueden ser soluci\'on, solo contando las soluciones que utilicen todas las fichas.\\
Puede verse luego que, para tableros m\'as grandes el nivel de complejidad aumenta dr\'asticamente. As\'i por ejemplo, para un tablero de $3$x$3$ existir\'an $9!= 362880$ posibles combinaciones, sin siquiera contar los casos en los que el tablero no se puede completar.









\newpage
\section{Idea General de Resoluci\'on}

Dado el crecimiento factorial de las posibles soluciones de este problema, utilizar metodos de fuerza bruta resultar\'ia extremadamente costoso, resultando en algoritmos lentos, y poco eficientes. 
\\
\\
Por esta razon (y por que lo pide el tp) se adoptar\'a la estrategia de backtraking para la resoluci\'on del problema. Esto quiere decir que iremos construyendo soluciones parciales de manera recursiva hasta alcanzar una soluci\'on total, la cual se verifica para ver si es o no la mejor hasta el momento.
\\
\\
Como buen algoritmo de backtracking, iremos realizando podas que permitir\'an desechar varias soluciones y as\'i disminuir los tiempos de ejecuci\'on.
\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{void FuncionPrincipal()}

  \STATE{Leer las entradas, crear el $tablero$ y  el $vector <Piezas>$}
  \STATE{Backtrack(t,piezas)}
  \STATE{Mostar El Tablero}
 \end{algorithmic}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{Bool Backtrack(t, piezas)}

  \STATE{Iniciar la funci\'on recursiva que va construyendo las posibles soluciones.}
  	\STATE{\quad Si llega al final de un tablero se fija si el tablero est\'a completo.}
  	\STATE{\quad Si lo esta, el algoritmo termina y devuelve la soluci\'on.}
	\STATE{\quad Si no, se fija si la soluci\'on es la mejor de las obtenidas hastael momento, en caso de serlo la guarda.}
	\STATE{\quad Si la mejor soluci\'on hasta el momento tiene k casilleros vacios y el tablero que estamos llenando en esta iteraci\'on tiene mas de k casilleros vacios, se realiza una poda en esa rama}
	\STATE{\quad Analiza las piezas posibles que pueden ir en la proxima posicion, esto es, las que coinciden con los colores hasta ahora puestos en el tablero}
		\STATE{\quad \quad Para cada una de esas piezas, construye una soluci\'on y llama otra vez a la funcion recursiva.}
		\STATE{\quad \quad Si ninguna de las piezas completa el tablero, deja ese casillero vac\'io y llama a la funci\'on recursiva.}

\end{algorithmic}
\end{algorithm}

\subsection{Justificaci\'on}

Nuestro algoritmo recorre todas las posiciones del tablero empezando por la casilla [0][0] hasta la [n-1][m-1].\\
Para cada casilla se fija que piezas se pueden colocar en la misma (chequea que coincidan los colores y que no hayan sido usadas en esa rama de solucion antes) y para cada posible pieza (dejarla vacia tambi\'en es una \'opcion v\'alida) la coloca en dicha casilla y genera otra rama de soluciones hasta llegar a la \'ultima posici\'on del tablero.
Luego, de todos los tableros generados nos quedaremos con el que mayor cantidad de piezas tenga.
\\
\\
Esto, as\'i tal cual lo dijimos estar\'ia iterando todas las combinaciones posibles de tableros y no ser\'ia un algoritmo de backtracking porque no estamos podando en ninguna parte.
\\
Las podas que realizamos para mejorar la performance son las siguientes:
\begin{itemize}
\item Si ya tengo un tablero completo con k casilleros vacios. Si en las soluciones que voy formando alguna queda con mas de k casilleros vacios, corto la rama de soluciones, ya que no voy a poder formar un tablero con mas piezas que el que tenia.
\item Si en alguna iteraci\'on se llega a formar una cruz con cuatro casillas blancas corto esa rama (ya que seguro encontrar\'e una soluci\'on mejor con la casilla del centro de la cruz llena).
\item Corto la rama si se completo la primer fila o columna con casillas vacias, o un par de filas/columnas consecutivas. Esto es porque si existe una solucion que admite dos filas o columnas o filas vac\'ias, es obvio que tambien admite una soluci\'on con una fila no vac\'ia intercalada entre estas dos que será, igual o mejor.
\end{itemize}



\newpage

\section{Cota de Complejidad}
Para poder dar una cota de complejidad es necesario estudiar el c\'odigo. 
En este ejercicio la funci\'on principal es la funci\'on \textit{backtracking}, que llama a la funci\'on \textit{recursi\'on}.
\\
La funcion \textit{recursion} hace la magia y se llama recursivamente, probando todas las combinaciones posibles de las fichas, y guardando la mejor soluci\'on.
 Para entender la complejidad vamos a dar un brebe pseudoc\'odigo de la funci\'on \textit{recursion}:
los parametros son:
tablero: $t$,  tableroOptimo: $t\_opt$,  vector$<piezas>$: vect,  
eje\_ x : $pos\_x$, eje\_ y : $pos\_y$.
\\ 
\subsection{Pseudoc\'odigo}
\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm

\caption{bool recursion($t, t\_opt , vect, pos\_x, pos\_y)$}

  \IF{estoy al final de fila} 
	\STATE{ubico el tablero al comienzo de la siguiente ($pos\_x = pos\_x+1, pos\_y=0$) ~~~~~~~~~~~~ $O(1)$}
  \ENDIF
  
  \STATE{\textbf{Si} estoy en el ultimo casillero ($pos\_x == n, pos\_y == m$ ~~~~~~~~~~~~ $O(1)$)}  
    \STATE{{~~~~\textbf{Si} complete el tablero con todas las piezas}
	\STATE {~~~~~~~~devuelvo true}
	\STATE {~~~~~~~~(no es necesario actualizar $t\_opt$ ya que el tablero completo es el mejor caso, el algoritmo termina ac\'a)}
    \STATE{~~~~\textbf{Sino si} termino con mas piezas que t\_optimo} 
	\STATE{~~~~~~~~t\_opt $<-$ t~~~~~~~~~~~~ $O(1)$} 
    \STATE{~~~~\textbf{Sino} retornar falso} 
	
	\STATE{armo un vector con piezasCandidatas que pueden encajar en posicion detablero actual ~~~~ $O(n.m)$} 
	
	\STATE{\textbf{Para Todo} i $\in$ Candidatas ~~~~~~~~~~~~  ($n.m$) llamadas} 
		\STATE{~~~~coloco pieza $i$ en posicion actual}
		\STATE{~~~~marco la ficha como utilizada}
		\STATE{~~~~\textbf{Si} recursion($t, t\_opt , vect, pos\_x, pos\_y + 1$)}
		\STATE{~~~~~~~~retorno true}
		
		\STATE{~~~~\textbf{si no}}
		\STATE{~~~~~~~~desmarco la ficha como utilizada}
		\STATE{~~~~~~~~saco la pieza del lugar actual para probar con la siguiente}

 \STATE{al salir de bucle, recursion($t, t\_opt , vect, pos\_x, pos\_y + 1$)}
 \STATE{(Osea el caso en que dejo el casillero vac\'io)}
    

\end{algorithmic}
\end{algorithm}
\\
\\
El analisis de complegidad de este algoritmo resulta bastante dificil de realizar dadas algunas particularidades inerentes al problema. Para empezar descartamos que el algoritmo dependa de $t\_opt$, dado que estamos calculando la cota de comlegidad del peor caso suponemos que vamos a entrar a todas las llamadas posibles y que no es posible podar nada.
\\
Asi la formula recursiva para calcular la cota de complegidad viene dada por:
$$T(w,x,y) = w.T(w-1,x,y+1) + T(w,x,y+1) + O(n.m) + O(1)$$
Donde $w$ son las piezas candidatas, y $x,y$ las coordenadas, que ir\'an recorrieno la matriz.
\\
Con el siguiente caso base:
$$T(w,n,m) =O(1)$$
\\
\\
Por una cuestion de simplificacion del analisis, en vez de escribir $n,m$ como parametros separados los escribo juntos. Viendo como funciona el algoritmo, se puede notar que esto no cambia la funcion de recurrencia.
$$T(w,x+y) = w.T(w-1,x+y+1) + T(w,x+y+1) + O(n.m) + O(1) = w.T(w-1,x+y+1) + T(w,x+y+1) + O(n.m)$$
Con el siguiente caso base:
$$T(w,n+m) =O(1)$$
Hago un cambio de parametro tal que:
$$ j = (m+n-x-y)$$
\\
Entonces,
$$T(w,j) = w.T(w-1, j-1) + T(w,j-1) + O(n.m) + O(1)$$
Con el siguiente caso base:
$$T(w,0) =O(1)$$
\\
\\
Veamos ahora, algunos casos para ver como se pude acotar:
$$T(w,0) = O(1)$$
$$T(w,1) = w.T(w-1,1-1)+ T(w,1-1) + O(n.m)= w.O(1) + O(1)+ O(n.m)$$
Como $w \leq n.m$, asi que acotando de manera un poco grosera $w = n.m$
$$T(w,1) = O(n.m)$$
\\
\\
$$T(w,2) = w.T(w-1,1)+ T(w,1) + O(n.m)$$
$$T(w,2) = w.O(n.m)+ O(n.m) + O(n.m) = O(n^2.m^2)$$
\\
\\
$$T(w,3) = w.T(w-1,2)+ T(w,2) + O(n.m)$$
$$T(w,3) = w.O(n^2.m^2)+ O(n^2.m^2) + O(n.m) = O(n^3.m^3)$$
\\
\\
De aquí puedo deducir que:
$$T(w,j) = O((m.n)^{j})$$
\\
\\
Ahora probandolo de manera formal por inducci\'on.
Paso base:
$$T(w,0) = O((m.n)^{0})= O(1)$$
Entonces cumple.
\\
\\
Paso inductivo:
Si $T(w,j-1)$ y $T(w-1,j-1)$ cumplen, quiero ver que $T(w,j)$ cumple.
$$T(w,j) = w.T(w-1,j-1)+ T(w,j-1) + O(n.m)$$
Hipotesis inductiva:
$$T(w,j) = w.O((n.m)^{j-1})+ O((n.m)^{j-1}) + O(n.m)$$
Aplicado la cota para $w$
$$T(w,j) = (n.m).O((n.m)^{j-1})+ O((n.m)^{j-1}) + O(n.m) = O((n.m)^{j})$$
Luego Cumple.
\\
\\
Entonces la complegidad para una entrada de $n.m$ es $O((n.m)^{n.m})$
\newpage

\section{Testing}
\subsection{Caso Random}

Para testear la correctitud emp\'irica de nuestro algoritmo se cre\'o un generador de entradas que fabricar\'a 50 instancias random de tableros de 4x4 y comparara nuestra salida con la de el mismo algoritmo, pero sin utilizar las podas, que resolviera el problema utilizando fuerza bruta pero, al no podar, con una complejidad mas alta.\\
\\
Los resultados comprobaron que nuestro algoritmo devuelve la soluci\'on correcta en todos los casos.
\\
\\
Ejemplo de caso random: (Este en particular tambi\'en fue verificado a mano)
\\
\\
\begin{tabular}{| l | l |}
\hline
~~~~~Entrada\\ \hline
$
\begin{vmatrix}
~~4  & 4  & 5  &   ~~ \\
~~1  & 2  & 2  & 3 ~~ \\
~~5  & 5  & 4  & 1 ~~ \\
~~1  & 5  & 2  & 4  ~~\\
~~4  & 1  & 5  & 3  ~~\\
~~2  & 2  & 3  & 4  ~~\\
~~3  & 1  & 4  & 4  ~~\\
~~3  & 4  & 1  & 2  ~~\\
~~4  & 3  & 3  & 1  ~~\\
~~1  & 3  & 1  & 2  ~~\\
~~5  & 4  & 3  & 1  ~~\\
~~1  & 2  & 1  & 4  ~~\\
~~4  & 5  & 1  & 2  ~~\\
~~2  & 2  & 2  & 3  ~~\\
~~2  & 3  & 1  & 5  ~~\\
~~4  & 4  & 2  & 3  ~~\\
~~4  & 3  & 5  & 3  ~~\\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~~~~~~Salida\\ \hline
$
\begin{vmatrix}
~~16 & 3  & 13 & 11 ~~\\
~~7  & 4  & 0  & 8 ~~ \\
~~14 & 6  & 10 & 9 ~~ \\
~~2  & 15 & 1  & 5 ~~ \\
\end{vmatrix}
$
\\ \hline
\end{tabular}


\subsection{Menor cantidad posible}

\begin{tabular}{| l | l |}
\hline
~~~~~Entrada\\ \hline
$
\begin{vmatrix}
~~3  & 3  & 9  &   ~~\\
~~1  & 1  & 1  & 1~~\\
~~2  & 2  & 2  & 2~~\\
~~3  & 3  & 3  & 3~~\\
~~4  & 4  & 4  & 4~~\\
~~5  & 5  & 5  & 5~~\\
~~6  & 6  & 6  & 6~~\\
~~7  & 7  & 7  & 7~~\\
~~8  & 8  & 8  & 8~~\\
~~9  & 9  & 9  & 9~~\\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~Salida\\ \hline
$
\begin{vmatrix}
~~1  & 0  & 2 ~~\\
~~0  & 3  & 0 ~~ \\
~~4  & 0  & 5 ~~ \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\\
\\
\\
Se corresponde al caso borde donde ninguna pieza puede ser colocada al lado de otra. 
\\
Luego, la cantidad de piezas colocadas en el tablero soluci\'on ser\'a la m\'inima posible.

\subsection{Dos soluciones \'optimas completas}

\begin{tabular}{| l | l |}
\hline
~~~~~Entrada\\ \hline
$
\begin{vmatrix}
~~ 3  & 3  & 4  &   ~~ \\
~~ 1  & 2  & 2  & 3 ~~ \\
~~ 2  & 1  & 4  & 1 ~~ \\
~~ 1  & 3  & 2  & 4 ~~ \\
~~ 4  & 1  & 2  & 3 ~~ \\
~~ 2  & 2  & 3  & 4 ~~ \\
~~ 3  & 1  & 4  & 4 ~~ \\
~~ 3  & 4  & 1  & 2 ~~ \\
~~ 4  & 3  & 3  & 1 ~~ \\
~~ 4  & 3  & 1  & 2 ~~ \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~Salida\\ \hline
$
\begin{vmatrix}
~~2  & 7  & 6 ~~\\
~~3  & 5  & 8 ~~ \\
~~9  & 4  & 1 ~~ \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
Otra Solucion\\ \hline
$
\begin{vmatrix}
~~3  & 5  & 8 ~~\\
~~9  & 4  & 1 ~~ \\
~~2  & 7  & 6 ~~ \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\\
\\
\\
Hay m\'as de una manera de rellenar completamente el tablero. Nuestro algoritmo siempre devolver\'a la que haya encontrado primero.

\subsection{Una sola fila o columna}


\begin{tabular}{| l | l |}
\hline
~~~~~Entrada\\ \hline
$
\begin{vmatrix}
~~1  & 5  & 4 ~~\\
~~1  & 2  & 2  & 3 ~~ \\
~~2  & 1  & 4  & 1 ~~ \\
~~1  & 3  & 2  & 4 ~~ \\
~~4  & 1  & 2  & 3 ~~ \\
~~2  & 2  & 3  & 4 ~~ \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~~~Salida\\ \hline
$
\begin{vmatrix}
~~1  & 5  & 3  & 0  & 2 ~~\\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
~~~~~Entrada\\ \hline
$
\begin{vmatrix}
~~5  & 1  & 4 ~~\\
~~1  & 2  & 2  & 3 ~~ \\
~~2  & 1  & 4  & 1 ~~ \\
~~1  & 3  & 2  & 4 ~~ \\
~~4  & 1  & 2  & 3 ~~ \\
~~2  & 2  & 3  & 4 ~~ \\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\quad \quad \quad
\begin{tabular}{| l | l |}
\hline
Salida\\ \hline
$
\begin{vmatrix}
~~1 ~~\\
~~0 ~~\\
~~2 ~~\\
~~3 ~~\\
~~4 ~~\\
\end{vmatrix}
$
\\ \hline
\end{tabular}
\\
\\
\\
Nos aseguramos que nuestro algoritmo no falle en los casos bordes donde solo hay una fila en el tablero o una sola columna.

\newpage
\section{Resultados}

En primera instancia se decidi\'o testear los tiempos ejecuci\'on de nuestro algoritmo para tableros de 4x4 pero variando la cantidad de colores diferentes de las piezas, diferenciando los casos en los que se pudo completar completamente el tablero (instancias\_si) de los que no (instancias\_no).
\\
\\
\includegraphics[width=18cm]{./rompecolores/graph_ej3_1.png}
\\
\\
Como podemos ver, cuantos menos colores diferentes haya, el algoritmo tardar\'a m\'as (excepto cuando haya uno solo y la soluci\'on sea trivial). \\
Esto se debe a que a la hora de colocar una pieza en una determinada posici\'on del tablero habr\'a muchas m\'as piezas que satisfagan las condiciones neceserias para ser candidatos (Porque tiene mas probabilidades de que coincidan los colores), generando muchas m\'as recursiones en nuestro algoritmo.


\newpage
Luego graficamos los tiempos de ejecuci\'on con respecto a la cantidad de piezas. Se decidi\'o dejar la cantidad de colores fija en 4.
\\
\\
\includegraphics[width=18cm]{./rompecolores/graph_ej3_2.png}
\\
\\
Como era de esperarse los tiempos aumentan de manera exponencial con respecto a la cantidad de piezas. 
\\
\\
Luego graficamos los tiempos de ejecuci\'on comparando el algoritmo con podas y sin podas. Se decidi\'o dejar la cantidad de colores fija en 4.
\\
\\
\includegraphics[width=18cm]{./rompecolores/graph_ej3_3.jpg}

\newpage

\section{Adicionales}
Versión 2.0 del \textit{Rompecolores}, se jugará ahora sobre un tablero toroidal. 
El tablero seguira siendo una grilla de \textit{n} filas y \textit{m} columnas, pero de forma modular.
La fila 1 justo debajo de la fila n y columna 1 justo a la derecha de la columna m.
Se pide desarrollar los siguientes puntos:

\begin{enumerate}
\item ¿Cómo debería modificarse el algoritmo implementado para que el mismo funcione en el \textit{Rompecolores 2.0}?. 

\begin{itemize}
\item En nuestro algoritmo original, vamos recorriendo el tablero linealmente (desde la casilla (0,0), hasta la casilla(n-1,m-1)), en cada casilla probamos con todas las piezas que quepan en ella y hacemos la recursión pasando a la siguiente casilla.
\item Si al estar parado en una casilla después de probar con todas las piezas posibles, no logramos completar el tablero, dejamos la casilla en blanco y seguimos con la siguiente posición.
\item Asi hasta haber probado todas las combinaciones posibles (con las respectivas podas de por medio).
\item Antes de colocar una ficha en una casilla, nos aseguramos de que sea compatible con las casillas vecinas. Si la casilla se encuentra en un borde(supongamos el izquierdo), en principio no nos preocupa el color del lado izquierdo de la ficha a poner.
\item Esta sería la principal modificación al tablero, ya que no existirian bordes. Ajustar las operaciones de comparación sería el primer cambio.
\item Es cierto que el tablero es toroidal, pero eso no quita que asignemos un orden a cada casilla, como en el tablero original.
\item En principio cualquier casilla puede ser la primera. Eso no importa mucho, ya que al fijar un orden, lo estaría viendo como una matriz, y puedo aplicar el algoritmo original con los ajustes de comparaciones correctos para las fichas.
\item Si bien es cierto, puedo ir moviendo la matriz (orden del tablero) corriendo casillas hacia arriba, abajo, izquierda, derecha; no importa mucho; ya que si tablero en una posición del toroidal encuentra una solución óptima, también sera solución optima, para cualquier ubicación o corrimiento de la matriz.
\ 

\end{itemize}

\item ¿Como afecta el nuevo esquema a las podas implementadas en la primera versión?. 
\begin{itemize}
\item Hicimos 4 podas al algoritmo original.
\item La primera: si estando en alguna casilla me doy cuenta que con las que me quedan no logro un resultado mejor que el logrado hasta el momento, detengo la recursion y sigo por otra rama del backtracking.
\begin{itemize}
\item En este caso no afecta en nada. Dado que asignamos un orden a las casillas puedo seguir usando esta poda.
\end{itemize}
\item La segunda: Si en alguna iteración se llega a formar una cruz con cuatro casillas blancas corto esa rama del árbol de recursión  (ya que seguro encontrare una solución mejor con la casilla del centro de la cruz llena).
\begin{itemize}
\item En este caso tampoco afecta la nueva versión.
\end{itemize}
\item Tercera y Cuarta: cortar, si completo la primer fila o columna con casillas vacias, o un par de filas/columnas consecutivas.
\begin{itemize}
\item Aca si afecta, pero se puede solucionar, ya que al fijar un tablero podemos basarnos en ese orden para saber cuando se completo una fila/columna.
\end{itemize}
 
\end{itemize}

\end{enumerate}





